package _10_Recursion;
/**
 * 斐波那契数列 : 前两位是1,其他每一位都等于前两位的和
 * 
 * 方法传入的参数是位数,比如传入10,就是要计算第10位的值是多少
 * 
 * 1 1 2 3 5 8 13 21 34 55 89
 * 
 * @author lenovo
 * @Date 2020年6月29日
 * @Time 下午5:59:40
 */
public class Recursion_02 {

	public static void main(String[] args) {
		//获取当前系统时间对应的毫秒数(时间原点到现在的毫秒数)
		long startTime = System.currentTimeMillis();
		System.out.println(fibonacci(40));
		System.out.println(count);
		long endTime = System.currentTimeMillis();
		System.out.println("递归耗时 : " + (endTime - startTime));

		startTime = System.currentTimeMillis();
		m1(13);
		endTime = System.currentTimeMillis();
		System.out.println("循环耗时 : " + (endTime - startTime));
	}
	
	// 计数,记录递归执行的压栈个数
	static int count = 0;

	/**
	 * 使用递归完成
	 */

	public static int fibonacci(int n) {
		// 每次执行方法对计数+1
		count++;
		// 因为斐波那契数列,最少要1位,所以判断,小于1,返回-1
		if (n < 1) {
			return -1;
		}
		// 因为斐波那契数列的前两位都是1,所以判断,n如果是1或者是2,就直接返回1
		if (n == 1 || n == 2) {
			return 1;
		}
		// 除了前两位,每一位的值都等于前两位的和,所以第n位=(n-1)位+(n-2)位
		return fibonacci(n - 1) + fibonacci(n - 2);
		// return fibonacci(4) + fibonacci(3);n=5
		// return fibonacci(3) + fibonacci(2);n=4
		// return fibonacci(2) + fibonacci(1);n=2
	}

	/**
	 * for循环完成斐波那契数列,并打印前n位的值
	 */
	public static void m1(int i) {
		if (i < 1) {
			System.out.println("位数不正确!");
			return;
		}
		// 说明i一定不小于1
		if (i == 1 || i == 2) {
			System.out.println("第" + i + "位的值是 : 1");
			return;
		}

		// 到这里说明一定是大于第二位的
		// 先把第一位和第二位打印
		System.out.println("第一位的值是 : 1");
		System.out.println("第二位的值是 : 1");

		// 当前位的前两位的值,默认是第一位
		long l1 = 1;
		// 当前位的前一位的值,默认是第二位
		long l2 = 1;
		// 当前默认是第三位
		long l3 = l1 + l2;
		for (int j = 3; j <= i; j++) {
			l3 = l1 + l2;
			System.out.println("第" + j + "位的值是:" + l3);
			// 把l2赋值给l1这时候l1就表示当前j位的前1位
			l1 = l2;
			// 把l3赋值给l2这时候l2就表示当前j位的值
			l2 = l3;
		}
	}
}
